package com.sx.sx1.lintcode.day717;


import java.util.*;

public class LC29101 {

    public static void main(String[] args) {
        System.out.println(getSecondDiameter(new int[][]{{0,1,4},{0,2,7}})); //7
    }


    public static long getSecondDiameter(int[][] edge) {
        int n= edge.length;
        Map<Integer, Set<Info>> map = buildGraph(n+1,edge);
        Info point2path = bfs(0,map);
        Info nextPoint2path = bfs(point2path.data,map);
        Info thirdpoint2path = bfs(nextPoint2path.data,map);
        return Math.max(nextPoint2path.distance,thirdpoint2path.distance);
    }

    public static Info bfs(int root,Map<Integer,Set<Info>> map){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(root);
        Map<Integer,Long> distanceToRoot = new HashMap<>();
        distanceToRoot.put(root,0L);
        int nodeFirst = root,nodeSecod = root;
        while (!queue.isEmpty()){
            int curNode = queue.poll();
            Set<Info> nexts = map.get(curNode);
            for(Info next: nexts){
                if(distanceToRoot.containsKey(next.data)) continue;

                long distance = distanceToRoot.get(curNode)+ next.distance;
                if(distance> distanceToRoot.get(nodeFirst)){
                    nodeSecod = nodeFirst;
                    nodeFirst = next.data;
                }else if(distance> distanceToRoot.get(nodeSecod)){
                    nodeSecod= next.data;
                }

                distanceToRoot.put(next.data,distance);
                queue.offer(next.data);
            }
        }

        return new Info(nodeFirst,distanceToRoot.get(nodeSecod));

    }


    public static Map<Integer,Set<Info>> buildGraph(int n,int[][] edge){
        Map<Integer,Set<Info>> ans = new HashMap<>();  //简历图
        for (int i = 0; i <n ; i++) {
            ans.put(i,new HashSet<>());
        }

        for(int[] item: edge){
            ans.get(item[0]).add(new Info(item[1],item[2]));
            ans.get(item[1]).add(new Info(item[0],item[2]));
        }

        return ans;
    }


    static class Info{
        long distance;
        int data;
        public Info(int d,long dd){
            distance=dd;
            data=d;
        }
    }

}

/*
解题思路
注意本地的 distance 会 int 越界，所以需要用long 来存储第一、第二距离。

题解代码
java
public class Solution {
    /**
     * @param edge: edge[i][0] [1] [2]  start point,end point,value
     * @return: return the second diameter length of the tree
     */
    /*
public long getSecondDiameter(int[][] edge) {
    int n = edge.length;
    Map<Integer, Set<Pair>> graph = buildGraph(n + 1, edge);
    Pair pointSed2Path = bfs(0, graph);
    Pair nextPointSed2Path = bfs(pointSed2Path.end, graph);
    Pair thirdPointSed2Path = bfs(nextPointSed2Path.end, graph);

    return Math.max(nextPointSed2Path.val, thirdPointSed2Path.val);
}

    private Pair bfs(int root, Map<Integer, Set<Pair>> graph){
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(root);
        Map<Integer, Long> distanceToRoot = new HashMap<>();
        distanceToRoot.put(root, 0L);

        int nodeFirst = root, nodeSecond = root;
        while (!queue.isEmpty()){
            int curNode = queue.poll();

            Set<Pair> neighbors = graph.get(curNode);
            for (Pair neighbor: neighbors) {
                if (distanceToRoot.containsKey(neighbor.end)){
                    continue;
                }
                long distance = distanceToRoot.get(curNode) + neighbor.val;
                if (distance > distanceToRoot.get(nodeFirst)){
                    nodeSecond = nodeFirst;
                    nodeFirst = neighbor.end;
                }else if (distance > distanceToRoot.get(nodeSecond)){
                    nodeSecond = neighbor.end;
                }
                distanceToRoot.put(neighbor.end, distance);
                queue.offer(neighbor.end);
            }
        }
        return new Pair(nodeFirst, distanceToRoot.get(nodeSecond));
    }

    private Map<Integer, Set<Pair>> buildGraph(int n, int[][] edge){
        Map<Integer, Set<Pair>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new HashSet<>());
        }
        for (int[] item : edge) {
            graph.get(item[0]).add(new Pair(item[1], item[2]));
            graph.get(item[1]).add(new Pair(item[0], item[2]));
        }
        return graph;
    }

class Pair{
    int end;
    long val;
    public Pair(int end, long val){
        this.end = end;
        this.val = val;
    }
}
}
        觉得这篇题解对你有
 */
/*
LintCode-Logo
学习
刷题
题集
群组
内推
VIP
CAT
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
您有334条未读消息，请及时查看
291 · 第二直径
算法
中等
通过率
40%
题目
题解8
笔记
讨论20
排名
记录
描述
给出由
�
n个结点，
�
−
1
n−1条边组成的一棵树。求这棵树的第二直径，也就是两两点对之间距离的次大值。
给出大小为
(
�
−
1
)
×
3
(n−1)×3的数组edge,edge[i][0],edge[i][1],edge[i][2],表示第i条边是从edge[i][0]连向edge[i][1]，长度为edge[i][2]的无向边。

北美在招WLB&高薪厂面经曝光

微信加sunny【jiuzhang1104】备注【在招】即可领取


2
≤
�
≤
1
0
5
2≤n≤10
5


1
≤
�
�
�
�
[
�
]
[
2
]
≤
1
0
5
1≤edge[i][2]≤10
5


因为DFS(Depth-First-Search)容易爆栈，请使用BFS(Breadth First Search)完成该题目
如果有多个点对的距离都是最长，那么你只需要返回最长距离即可~

样例
输入:[[0,1,4],[0,2,7]]
输出:7
解释:两两之间的次大值为0到2的7

标签
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
-/-
已开启智能提示
发起考试
30 分 00 秒
123456789
public class Solution {
    /**
     * @param edge: edge[i][0] [1] [2]  start point,end point,value
     * @return: return the second diameter length of the tree
     */

    /*
public long getSecondDiameter(int[][] edge) {
    // write your code here
}
}
控制台
        历史提交

 */
